// hdu5956
// 题意：给定n(<=500000)个数，要将它分成一段一段打印，每一段打印的费用为
//       (sigma(ai))^2 + m，求最小的打印费用。
//
// 题解：首先容易得到一个dp，dp[i] = dp[j] + (sum[i] - sum[j])^2 + m，
//       不过复杂度不够，考虑优化。
//       对于k<j<i，若
//        dp[j] + (sum[i]-sum[j])^2 + m <= dp[k] + (sum[i] - sum[k])^2 + m
//       推出
//        dp[j] + sum[j]^2  -  (dp[k] + sum[k]^2)
//        --------------------------------------- <= sum[i]
//                  2*sum[j] - 2*sum[k]
//       我们令Yi=dp[i] + sum[i]^2, Xi=2*sum[i],式子就可以改写成
//       (Yj - Yk)/(Xj - Xk) <= sum[i]，
//       如果把(Xi, Yi)看作一个点，其中左边是斜率，右边是个单调递增（不减，稍后特殊讨论），
//       的函数。我们令slope[j, k]=(Yj - Yk)/(Xj - Xk),
//       1.首先如果slope[j, k]<=sum[i], 我们说当前决策点j比k优，并且sum一直
//         递增，接下来也一直比k优;
//       2.考虑k<j<i, 如果slope[i, j]<slope[j, k]我们说j不会成为最优点，
//        i).如果slope[i, j]<=sum[i]，那么，i比j优，
//        ii).如果slope[i, j]>sum[i]，那么slope[j, k]>sum[i]，故考虑上面
//            最优推导（反一下不等号），k比j优，所以最优决策肯定构成一个
//            下凸图形。
//
//       然后就可以用单调队列来维护这个下凸壳，每次现将队首不够优的状态
//       剔除，然后加入新点，维护下凸性（不断剔除对尾）。
//       要注意的是这题的数可以为0, 所以可能有相同的点存在，这个斜率是不存在的，
//       所以将上面第2个里面的小于号改成小于等于即可。算斜率也不要直接算，
//       用叉积。
//
//       这题是树上的情况，那么只需要将单调队列可持久化就行，这里的可持久化
//       非常简单，恢复的时候可以做到O(1)，因为虽然单调队列修改了很多，但是
//       实际修改的值只有一个，所以维护这个值就行。
//
// 统计：390ms, 4wa
//
// ml:run = $bin < input
#include <cstdio>
#include <vector>

using ll = long long;
int const maxn = 500100;
long long sum[maxn];
long long dp[maxn];
int q[10 * maxn];
int n, head, tail;
ll p, ans;

struct edge { int to, c; };
std::vector<edge> g[maxn];

ll coord_y(int i) { return sum[i] * sum[i] + dp[i]; }
ll coord_x(int i) { return 2 * sum[i]; }
ll slope_y(int i, int j) { return coord_y(i) - coord_y(j); }
ll slope_x(int i, int j) { return coord_x(i) - coord_x(j); }

bool slope_less(int i1, int j1, int i2, int j2)
{   //                                       |
	//                                       v this <= change to < will wa, because of the zero number, there maybe two same point.
	return slope_y(i1, j1) * slope_x(i2, j2) <= slope_y(i2, j2) * slope_x(i1, j1);
}

void init()
{
    for (int i = 0; i <= n; i++)
        g[i].clear();
    ans = 0;
}

void add_edge(int u, int v, int w)
{
    g[u].push_back({v, w});
    g[v].push_back({u, w});
}

void dfs(int u, int father = 0)
{
    ans = std::max(ans, dp[u]);
    for (auto e : g[u]) {
        int v = e.to; ll c = e.c;
        if (v == father) continue;
        sum[v] = sum[u] + c;
        dp[v] = sum[v] * sum[v];
        int bhead = head, btail = tail;
        while (head < tail && slope_y(q[head+1], q[head]) <= sum[v] * slope_x(q[head+1], q[head])) head++;

        int j = q[head];
        dp[v] = std::min(dp[v], dp[j] + (sum[v] - sum[j]) * (sum[v] - sum[j]) + p);

        while (head < tail && slope_less(v, q[tail], q[tail], q[tail - 1])) tail--;
        int bpos = tail + 1;
        int bv = q[tail + 1];
        q[++tail] = v;

        dfs(v, u);

        head = bhead;
        tail = btail;
        q[bpos] = bv;
    }
}

int main()
{
    int T; std::scanf("%d", &T);
	while (T--) {
        std::scanf("%d%lld", &n, &p);
        init();
        for (int i = 1; i < n; i++) {
            int u, v, w; std::scanf("%d%d%d", &u, &v, &w);
            add_edge(u, v, w);
        }

		head = 1, tail = 1;
		q[head] = 0;
        dp[1] = 0;
        dfs(1);
		std::printf("%lld\n", ans);
	}
}

